1. Technical Field Text
The present invention relates to arithmetic coding and in particular to method and apparatus for termination of arithmetic coding.
2. Background Information
Arithmetic coding has been successfully applied to compression of media data such as images, and audio. The newest video coding standard H.264/AVC proposed by the ITU-T and MPEG, which is incorporated herein by reference, achieves a significant performance improvement over previous coding standards such as H.263 and MPEG 2. H.264/AVC standard supports two different entropy coding methods, i.e., Context-based Adaptive Variable Length Coding (CAVLC) and Context-based Adaptive Binary Arithmetic Coding (CABAC). Compared with CAVLC, CABAC provides higher coding efficiency at average bit rate saving of 9%-14%. See Li Liu and Xinhua Zhuang “CABAC Based Bit Estimation for First H.264 Rd Optimization Decision,” IEEE, 2009, which is incorporated herein by reference.
The basic idea of the CABAC encoding process is recursive interval division. The CABAC engine keeps two registers. The first register is a range register with 9-bits. The second register is an offset register which is 9-bits in a regular mode and 10-bits in a bypass mode. The range register keeps track of the width of the current interval. The offset is from the bit-stream and points to the current location within the range. When decoding a bin, the range is divided into two subintervals depending on the probability of occurrence unique to the bin. After the bin is decoded, the range and offset are updated. After decoding one bin, range and offset will be renormalized to keep the precision to decode a next bin. It ensures the most significant bit of the 9 bit register range is always 1.
Termination of arithmetic encoding typically occurs when the arithmetic encoder reaches the end of a slice. Since the number of macroblocks in a slice is variable, for implementation of CABAC, H.264/AVC requires encoding of a terminating syntax element, called “end_of_slice_flag”, for each macro block in a slice to signal the end of a coded slice to the decoder. If a given macroblock is not the last macroblock in the slice, the flag is set to zero and signaled to the decoder, whereas a given macroblock is the last macroblock in the slice, the flag is set to one and signaled to the decoder. The flag is encoded using a specifically designated non-adaptive probability model such that the event of a non-terminating macroblock is related to the highest possible MPS probability. The end_of_slice_flag enables the decoder to determine whether the last macroblock in a coded slice has been decoded.
FIG. 1 shows a flowchart illustrating the CABAC encoding procedure before termination specified in the H.264/AVC standard. See FIG. 9-11 of H.264/AVC. In FIG. 1, the value of codIRange is decremented by 2 at Step 101. It is then determined at Step 102 whether the bin value (binVal) being encoded is not equal to zero. If the bin value is equal to zero, or if the bin includes an event of the terminating syntax element equal to zero, which means that the encoder has not reached the end of a slice, a renormalization procedure is performed at Step 103, and the terminating syntax element (=0) is encoded. If the bin value being encoded is not equal to zero, or if the bin includes an event of the terminating syntax element equal to one, which means that the encoder has reached the end of a slice, CABAC encoding is terminated, and the value of codILow is set to a sum of the values of codILow and codIRange at Step 104. The process then advances to Step 105, where an encoder flushing procedure is performed, and the terminating syntax element (=1) is encoded. An exemplary encoder flushing procedure is specified in FIG. 9-12 of H.264/AVC. Lastly, BinCountsInNALunits is incremented by 1 at Step 106.
FIG. 2 shows a flowchart illustrating the CABAC decoding process before termination specified in H.264/AVC. See FIG. 9-6 of H.264/AVC. In FIG. 2, the value of codIRange is decremented by 2 at Step 201. It is then determined at Step 202 whether the value of codIOffeset is greater than or equal to the value of codIRange. If not, the bin value is set to zero at Step 203, which means that the decoder has not reached the end of a coded slice. The process then advances to Step 204 to perform a renormalization procedure. If the value of codIOffeset is greater than or equal to the value of codIRange, which means that the decoder has reached the end of the coded slice, the bin value is set to one at Step 205, and the CABAC decoding process is terminated.
Please note that the encoding process shown in FIG. 1 is performed for each macroblock in a slice. Since repeated for the respective macroblocks in a slice, encoding of the terminating syntax element necessarily results in an increase of the bits in a bitstream, which is not desirable. Although the cost to pay for increased bits resulting from encoding the terminating syntax element may be considered not so large, it increases as the granularity of slices increases. For example, slices may be defined at an increased granularity, such as with 8×8 macroblocks, instead of traditional 16×16 macroblocks. An increase in the granularity is beneficial in that slices can be defined with the number of bits closer to a target number of bits. However, if the granularity is increased to 8×8 from 16×16, the overhand in bits increased by encoding the terminating syntax element becomes quadruple.